// 合并 k 个排序链表，返回合并后的排序链表
// 示例:
// 输⼊:
// [
//  1->4->5,
//  1->3->4,
//  2->6
// ]
// 输出: 1->1->2->3->4->4->5->6

// js中没有链表结构，所以需要模拟一个类似于链表的数据结构
class ListNode {
  constructor (val, next = null) {
    this.val = val
    this.next = next
  }
}

// 第一个链表
const list1 = new ListNode(1)
const node11 = new ListNode(4)
list1.next = node11
const node12 = new ListNode(5)
node11.next = node12

// 第二个链表
const list2 = new ListNode(1)
const node21 = new ListNode(3)
list2.next = node21
const node22 = new ListNode(4)
node21.next = node22

// 第三个链表
const list3 = new ListNode(2)
const node31 = new ListNode(6)
list3.next = node31

let arr = []
arr.push(list1)
arr.push(list2)
arr.push(list3)

// console.log(arr.length)

function mergeKLists (list) {
  if (!list.length) {
    return null
  }

  const merge = function (l1, l2) {
    if (l1 === null) {
      return l2
    }
    if (l2 === null) {
      return l1
    }
    if (l1.val < l2.val) {
      l1.next = merge(l1.next, l2)
      return l1
    } else {
      l2.next = merge(l1, l2.next)
      return l2
    }
  }

  function mergetwo (lists, start, end) {
    // 第一次进入(list,0,3) 这时mid为1
    // 然后进入命名head1的部分，参数为(list,0,1)
    // head1=list[0]
    // 进入head2的命名 参数为(list,1,3) 
    // 不能直接返回，需要生成新的链表，此时mid为2
    // 重新调用了mergetwo，head1 = mergetwo(lists, 1, 2) 留出list[1]
    // head2 = mergetwo(lists, 2, 3) 留出list[2]
    // 这样 第一次的head2这个循环就需要两个链表来合并，就是这个 list[1]和list[2]
    // 如果 start + 1= end 说明分隔的只剩下两个了，返回第一个，第二个在head2中他也是第一个
    // 所以第二个也会被返回，不会少
    if (start + 1 == end) {
      return lists[start]
    }
    // >> 1相当于将前面的值除以2并向下取整
    let mid = (start + end) >> 1
    console.log('mid', mid)
    let head1 = mergetwo(lists, start, mid)
    let head2 = mergetwo(lists, mid, end)
    return merge(head1, head2)
  }

  return mergetwo(list, 0, list.length)
}

let m = mergeKLists(arr)

while (m !== null) {
  console.log(m.val)
  m = m.next
}
